"""
如果对调字符，使得单词 w 变成单词 v，那么 w 就是 v 的易位构词。
假设有一个集合包含了 n 个最大长度为 k 的单词，现在要找到所有的易位构词。

输入：le chien marche vers sa niche et trouve une limace de chine nue pleine de malice qui lui fait du charme

输出：{une nue}, {marche charme}, {chien chine niche}, {malice limace}.

句子的意思是：“一条狗走向狗窝时遇到一条顽皮的鼻涕虫，被吸引了过去。”其中某些单词，
如 chien（狗）和 niche（窝）、limace（鼻涕虫）和 malice（顽皮）等，
都是字母相同而顺序不同的单词，输出得到的是输入句子中所有易位构词的集合。
"""


def myAnagrams(word):
    word_li = list(set(word.split(" ")))  # 拆分并去重
    sort_word = {}
    result_dic = {}

    # 将每个单词按字母变列表并排序
    for i in word_li:
        sort_word[i] = sorted([a for a in i])

    # 按字母列表相同的组装字典
    for k, v in sort_word.items():
        if tuple(v) not in list(result_dic.keys()):
            result_dic[tuple(v)] = [k]
        else:
            result_dic[tuple(v)].append(k)

    # 筛选易位构词
    result = [res for res in result_dic.values() if len(res) > 1]
    return result


def anagrams(w):
    """
    组装成这种形式方便提取易位构词 d: {'cehin': [0, 1, 6], 'ersv': [2], 'eortuv': [3], ..., 'eeilnp': [19]}

    ● 复杂度
        该算法能在平均时间 O(nklogk) 内解决问题。
        而在最坏情况下，由于使用了字典，所需时间复杂度是 O(n**2klogk)。

    ● 算法
        算法的思路是计算每个单词的签名。
        两个单词能得到相同的签名，当且仅当它们互为易位构词。
        这个签名不过是包含了相同字母的另一个单词，是把要计算签名的单词中的所有字母按顺序排列后得到的。
        算法使用的数据结构是一个字典，将每个签名与拥有这一签名的所有单词的列表对应起来。
    """
    w = list(set(w.split(" ")))  # 删除重复项
    d = {}  # 保存有同样签名的单词
    for i in range(len(w)):
        s = ''.join(sorted(w[i]))  # 签名
        if s in d:
            d[s].append(i)
        else:
            d[s] = [i]
    # -- 提取易位构词
    reponse = []
    for s in d:
        if len(d[s]) > 1:  # 忽略没有易位构词的词
            reponse.append([w[i] for i in d[s]])
    return reponse


if __name__ == '__main__':
    word = "le chien marche vers sa niche et trouve une limace de chine nue pleine de malice qui lui fait du charme"
    print(myAnagrams(word))
    print(anagrams(word))
    # test()
